1033D - Divisors - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MOD=998244353;
ll sqr_2(ll l,ll r,ll x){
    while(l<=r){
        auto mid=l+r>>1;
        if(mid*mid<=x) l=mid+1;
        else r=mid-1;
    }
    return l-1;
}
ll sqr_3(ll l,ll r,ll x){
    while(l<=r){
        auto mid=l+r>>1;
        if(mid*mid*mid<=x) l=mid+1;
        else r=mid-1;
    }
    return l-1;
}
ll gcd(ll A,ll B){
    if(B==0) return A;
    return gcd(B,A%B);
}
ll sqr_4(ll l,ll r,ll x){
    while(l<=r){
        auto mid=l+r>>1;
        if(mid*mid*mid*mid<=x) l=mid+1;
        else r=mid-1;
    }
    return l-1;
}
map<ll,ll>mp,mmp;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        ll x;
        scanf("%lld",&x);
        auto tmp=sqr_4(1,40000,x);
        if(tmp*tmp*tmp*tmp==x){
            mp[tmp]+=4;
            continue;
        }
        tmp=sqr_3(1,1300000,x);
        if(tmp*tmp*tmp==x){
            mp[tmp]+=3;
            continue;
        }
        tmp=sqr_2(1,1500000000,x);
        if(tmp*tmp==x){
            mp[tmp]+=2;
            continue;
        }
        bool flag=0;
        for(auto it:mp){
            if(x%it.first==0){
                mp[it.first]++;
                mp[x/it.first]++;
                flag=1;
                break;
            }
        }
        if(flag) continue;
        for(auto it:mmp){
            if(it.first==x){
                mmp[x]++;
                flag=1;
                break;
            }
            ll g=gcd(it.first,x);
            if(g==1) continue;
            mp[g]+=mmp[it.first]+1;
            mp[it.first/g]+=mmp[it.first];
            mp[x/g]++;
            mmp[it.first]=0;
            flag=1;
            break;
        }
        if(!flag) mmp[x]++;
    }
    for(auto it1:mmp){
        for(auto it2:mp){
            if(it1.first%it2.first==0){
                mp[it2.first]+=it1.second;
                mp[it1.first/it2.first]+=it1.second;
                mmp[it1.first]=0;
                break;
            }
        }
    }
    ll ans=1;
    for(auto it:mp){
        // cout<<it.first<<"  "<<it.second<<endl;
        ans=(ans*(it.second+1))%MOD;
    }
    for(auto it:mmp){
        ans=(ans*(it.second+1))%MOD;
        ans=(ans*(it.second+1))%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}